In this paper we consider neighborhood load balancing in the context ofselfish clients. We assume that a network of n processors and m tasks is given.The processors may have different speeds and the tasks may have differentweights. Every task is controlled by a selfish user. The objective of the useris to allocate his/her task to a processor with minimum load. We revisit theconcurrent probabilistic protocol introduced in [6], which works in sequentialrounds. In each round every task is allowed to query the load of one randomlychosen neighboring processor. If that load is smaller the task will migrate tothat processor with a suitably chosen probability. Using techniques fromspectral graph theory we obtain upper bounds on the expected convergence timetowards approximate and exact Nash equilibria that are significantly betterthan the previous results in [6]. We show results for uniform tasks onnon-uniform processors and the general case where the tasks have differentweights and the machines have speeds. To the best of our knowledge, these arethe first results for this general setting.
展开▼
